ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Algorithmus von Dinic</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Algorithmus von Dinic</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Algorithmus von Dinic ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> aus der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> zur Bestimmung eines <a href="Fl%C3%BCsse_und_Schnitte_in_Netzwerken" title="Flüsse und Schnitte in Netzwerken">maximalen Flusses in einem Netzwerk</a>. Er wurde von E. A. Dinic (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des <a href="Algorithmus_von_Edmonds_und_Karp" title="Algorithmus von Edmonds und Karp">Edmonds-Karp-Algorithmus</a>, den Dinic unabhängig von <a href="Jack_Edmonds" title="Jack Edmonds">Jack Edmonds</a> und <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen.

<div class="mw-heading mw-heading2"><h2 id="Der_Algorithmus">Der Algorithmus</h2></div>

Im Folgenden bezeichnet im Netzwerk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (G,u,s,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (G,u,s,t)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/291c3acf319fd75cb46fef6de9c01ec65922ca23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.998ex; height:2.843ex;" alt="{\displaystyle (G,u,s,t)}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> den gerichteten Graphen, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/13d7aed6c539f41fb769895b55c590173f6d3103.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.578ex; height:2.843ex;" alt="{\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}" loading="lazy"> die Kapazitätsfunktion (wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u(e)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u(e)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec88023e46f681b8a5d635bc292b230e4e1f7966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.222ex; height:2.843ex;" alt="{\displaystyle u(e)}" loading="lazy"> die Kapazität einer Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy"> angibt), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> den Knoten, von dem der Fluss startet, und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> den Zielknoten des Flusses. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ba39dee5fd7f4467e387af4026315fb1fb21628.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.423ex; height:2.843ex;" alt="{\displaystyle V(G)}" loading="lazy"> bezeichnet die Knotenmenge des Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9fe79ce568f84c67757cfb1b3c9660698e8b20a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.412ex; height:2.843ex;" alt="{\displaystyle E(G)}" loading="lazy"> die Kantenmenge. Zu einem Fluss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> den <a href="Residualgraph" class="mw-redirect" title="Residualgraph">Residualgraphen</a> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> den <a href="Fl%C3%BCsse_und_Schnitte_in_Netzwerken#Schichtnetzwerk" title="Flüsse und Schnitte in Netzwerken">Schichtgraphen</a>, also den Graphen, der sich mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> die Knotenmenge teilt und aus genau den Kanten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E(G_{f})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E(G_{f})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/887d5ee1e707e467076764c6770613fda88bbe58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.689ex; height:3.009ex;" alt="{\displaystyle (u,v)\in E(G_{f})}" loading="lazy"> besteht, die für beliebige Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> zu einem kürzesten s-v-Weg von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> gehören. Insbesondere enthält <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> auch alle Kanten, die zu einem kürzesten s-t-Weg in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> gehören. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0f1dd81abca1620bc42ed439b198dcfe95e350e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.466ex; height:2.343ex;" alt="{\displaystyle u_{f}}" loading="lazy"> bezeichnet die zum Residualgraph gehörige Residualkapazität. Ein Sperrfluss (auch blockierender Fluss genannt) in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> ist ein s-t-Fluss, der in jedem s-t-Weg in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> mindestens eine Kante auslastet. Zu einer Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dcbe07e4cf5a71281984b081acaff2f4749f0856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.336ex; height:2.843ex;" alt="{\displaystyle e\in E(G)}" loading="lazy"> bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overleftarrow {e}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overleftarrow {e}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/11d89f26cbb76adf9f3e9db8271170345cd87736.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.453ex; height:3.009ex;" alt="{\displaystyle {\overleftarrow {e}}}" loading="lazy"> die zugehörige Rückkante des Residualgraphen.

Der Algorithmus arbeitet wie folgt:

<ol><li>Setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(e):=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(e):=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6285023b39f490ab5d77a667395d83eae83be254.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.079ex; height:2.843ex;" alt="{\displaystyle f(e):=0}" loading="lazy"> für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dcbe07e4cf5a71281984b081acaff2f4749f0856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.336ex; height:2.843ex;" alt="{\displaystyle e\in E(G)}" loading="lazy">.</li>

<li>Bestimme den Schichtgraphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy">.</li>

<li>Bestimme einen Sperrfluss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy">.</li>

<li>Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> der Nullfluss ist, sind wir fertig, ansonsten augmentiere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> entlang <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> (d. h. für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E(G)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E(G)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dcbe07e4cf5a71281984b081acaff2f4749f0856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.336ex; height:2.843ex;" alt="{\displaystyle e\in E(G)}" loading="lazy"> setze: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(e):=f(e)+g(e)-g({\overleftarrow {e}})}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(e):=f(e)+g(e)-g({\overleftarrow {e}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31cf510b33941716504f1a8e45c94e119be308f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.156ex; height:3.509ex;" alt="{\displaystyle f(e):=f(e)+g(e)-g({\overleftarrow {e}})}" loading="lazy"> (mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(e):=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(e):=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43b0fa36f49e761aa5b80d6ee640684b02bd55f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.917ex; height:2.843ex;" alt="{\displaystyle g(e):=0}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\notin E(G_{f}^{L})}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\notin E(G_{f}^{L})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e4f05b1a5d14ceaee7227c1fff543902bd567736.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.687ex; height:3.509ex;" alt="{\displaystyle e\notin E(G_{f}^{L})}" loading="lazy">)) und springe zu 2.</li></ol>

Am Ende ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> ein maximaler s-t-Fluss, da es im Residualgraphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> keinen s-t-Weg mehr gibt.

<div class="mw-heading mw-heading3"><h3 id="Sperrfluss_finden">Sperrfluss finden</h3></div>

Für Schritt 3 des Algorithmus kann ein Sperrfluss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> beispielsweise wie folgt berechnet werden:

<ol><li>Setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(e):=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(e):=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43b0fa36f49e761aa5b80d6ee640684b02bd55f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.917ex; height:2.843ex;" alt="{\displaystyle g(e):=0}" loading="lazy"> für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71d92596090570ee4bf28e974297eb49b8df2983.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:7.102ex; height:3.509ex;" alt="{\displaystyle e\in G_{f}^{L}}" loading="lazy">.</li>

<li>Setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H:=G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H:=G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99d0e04b2eb3b6dc02aa47ce9c4a8a786b874b72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:8.987ex; height:3.509ex;" alt="{\displaystyle H:=G_{f}^{L}}" loading="lazy">.</li>

<li>START

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P:=[s]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/95b81e6322050daa7841973db3b81f9fe06e7f08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.875ex; height:2.843ex;" alt="{\displaystyle P:=[s]}" loading="lazy"> (Weg aus nur einem Knoten ohne Kanten)</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v:=s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55dab9fff7b1cc80bd484a529bfae0ec7a926ed4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.963ex; height:1.676ex;" alt="{\displaystyle v:=s}" loading="lazy"></li>

<li>springe zu VOR.</li></ul></li>

<li>VOR

<ul><li>Falls in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> keine Kante den Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> verlässt, springe zu ZURÜCK.</li>

<li>Anderenfalls

<ul><li>Wähle eine Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v,w)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe1ba70e3b2d314bc63be62afe1e5c3a80b95834.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.635ex; height:2.843ex;" alt="{\displaystyle (v,w)}" loading="lazy"> aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">.</li>

<li>Verlängere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v,w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v,w)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe1ba70e3b2d314bc63be62afe1e5c3a80b95834.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.635ex; height:2.843ex;" alt="{\displaystyle (v,w)}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v:=w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ead01db3266e631c99b502c09d3e2d53b131b607.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.537ex; height:1.676ex;" alt="{\displaystyle v:=w}" loading="lazy"></li>

<li>Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\neq t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\neq t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fd1666f632aafd273a8ace02e6a2ed34acb75cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.066ex; height:2.676ex;" alt="{\displaystyle v\neq t}" loading="lazy">, springe zu VOR.</li>

<li>Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v=t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v=t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91beec518a3d8feebf989d197f96aae1cc962a5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.066ex; height:2.009ex;" alt="{\displaystyle v=t}" loading="lazy">, springe zu AUGMENTIEREN.</li></ul></li></ul></li>

<li>AUGMENTIEREN

<ul><li>Augmentiere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> längs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> um so viel wie möglich (d. h. für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma :=\min _{e\in E(P)}u_{f}(e)}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma :=\min _{e\in E(P)}u_{f}(e)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea03f9d25b9186d77cdc243b1b2a0f12a4e55ce1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.385ex; height:4.509ex;" alt="{\displaystyle \gamma :=\min _{e\in E(P)}u_{f}(e)}" loading="lazy"> setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(e):=g(e)+\gamma \!\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(e):=g(e)+\gamma \!\,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4d699e5d5c8a7f7dd7e3a645a52efcbd0dbd156e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.866ex; height:2.843ex;" alt="{\displaystyle g(e):=g(e)+\gamma \!\,}" loading="lazy"> für jedes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E(P)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E(P)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d9f19df8656050d088bb4948cbb015acc93c8299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.254ex; height:2.843ex;" alt="{\displaystyle e\in E(P)}" loading="lazy">).</li>

<li>Entferne die Kanten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">, die dadurch ausgelastet werden.</li>

<li>Springe zu START.</li></ul></li>

<li>ZURÜCK

<ul><li>Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v=s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v=s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe7d6ff7be4db29cd5cb6ec52bcc87177e6989b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.317ex; height:1.676ex;" alt="{\displaystyle v=s}" loading="lazy">, ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> Sperrfluss, also STOP.</li>

<li>Anderenfalls

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy"> letzte Kante auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.</li>

<li>Verkürze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy">.</li>

<li>Entferne <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> und alle mit ihm inzidenten Kanten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v:=u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af04ceb567f2e3e9bf10ff1597447e0e24b907bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.203ex; height:1.676ex;" alt="{\displaystyle v:=u}" loading="lazy"></li>

<li>Springe zu VOR.</li></ul></li></ul></li></ol>

Am Ende dieses Verfahrens ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> Sperrfluss in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy">. Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=|E(G)|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=|E(G)|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c0d74ea7e8096177df15e828c7284d67545a3cef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.844ex; height:2.843ex;" alt="{\displaystyle m=|E(G)|}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=|V(G)|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=|V(G)|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d5a4b3d0c3521c9ca0765b4d35045c476c75916.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.21ex; height:2.843ex;" alt="{\displaystyle n=|V(G)|}" loading="lazy">. Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(nm)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(nm)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3489bc066cdb904706be9fa1ba069a7cb4062a89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.094ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(nm)}" loading="lazy">. Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> dieser Aufrufe (denn der Schichtgraph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> hat höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> Kanten). Weil der Schichtgraph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> keine gerichteten Kreise enthält, kann zwischen zwei AUGMENTIEREN-Aufrufen jeder Knoten höchstens einmal durch eine VOR-Operation erreicht werden, also werden insgesamt höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(nm)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(nm)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3489bc066cdb904706be9fa1ba069a7cb4062a89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.094ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(nm)}" loading="lazy"> solche durchgeführt; eine VOR-Operation kann in konstanter Laufzeit ausgeführt werden. In den ZURÜCK-Operationen wird jedes Mal ein Knoten entfernt, also werden sie höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n+m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n+m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/02dc3ad3931a7f098ba16dd445e724865fd5e392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.935ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n+m)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Anmerkung">Anmerkung</h3></div>

E. A. Dinic arbeitete statt mit dem Schichtgraphen mit einem Teilgraphen, der genau aus den Knoten und Kanten besteht, die auf kürzesten s-t-Wegen liegen. Die Verwendung des Schichtgraphen funktioniert analog, vereinfacht aber die Beschreibung des Algorithmus.

<div class="mw-heading mw-heading2"><h2 id="Laufzeit">Laufzeit</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=|E(G)|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=|E(G)|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c0d74ea7e8096177df15e828c7284d67545a3cef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.844ex; height:2.843ex;" alt="{\displaystyle m=|E(G)|}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=|V(G)|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=|V(G)|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d5a4b3d0c3521c9ca0765b4d35045c476c75916.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.21ex; height:2.843ex;" alt="{\displaystyle n=|V(G)|}" loading="lazy">. Der Algorithmus von Dinic benötigt höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> Durchläufe. Der Schichtgraph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> kann mit <a href="Breitensuche" title="Breitensuche">Breitensuche</a> in Laufzeit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/089694843af30c69c8b1d6287c3d8f0e2868499c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.7ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(m)}" loading="lazy"> berechnet werden. Ein Sperrfluss in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}^{L}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}^{L}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecd000f1bec05fa09bb6ee3a252398bd929f171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.178ex; height:3.509ex;" alt="{\displaystyle G_{f}^{L}}" loading="lazy"> kann mit der oben angegebenen Methode in Laufzeit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(nm)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(nm)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3489bc066cdb904706be9fa1ba069a7cb4062a89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.094ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(nm)}" loading="lazy"> berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2}m)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2}m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53235073d0d7c2af9365d5fda34d5de0261150f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.149ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2}m)}" loading="lazy">. Dies ist auch die Laufzeit, die von Dinic 1970 bewiesen wurde. Allerdings arbeitet der <a href="Goldberg-Tarjan-Algorithmus" title="Goldberg-Tarjan-Algorithmus">Goldberg-Tarjan-Algorithmus</a> schneller.

Mit einer Verbesserung von Alexander Karzanov von 1974 lässt sich für den Algorithmus von Dinic auch eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{3}+nm)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{3}+nm)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d2a3e51a2dac58cf741b92c73e5ee69b29175482.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.384ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{3}+nm)}" loading="lazy"> erreichen.

<div class="mw-heading mw-heading2"><h2 id="Quellen">Quellen</h2></div>

<ul><li><a href="Bernhard_Korte" title="Bernhard Korte">Bernhard Korte</a>, <a href="Jens_Vygen" title="Jens Vygen">Jens Vygen</a>: Kombinatorische Optimierung: Theorie und Algorithmen. Aus dem Englischen von Rabe von Randow. Springer-Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7</li>

<li>Helmut Alt: <a rel="nofollow" class="external text" href="http://www.inf.fu-berlin.de/lehre/WS06/HA/skript/skript.pdf">Vorlesungsskript Höhere Algorithmik, Wintersemester 2006/2007, Freie Universität Berlin.</a> (PDF; 2,5 MB)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>E. A. Dinic: <a rel="nofollow" class="external text" href="http://www.cs.bgu.ac.il/~dinitz/D70.pdf">Algorithm for solution of a problem of maximum flow in a network with power estimaton, 1970</a> (PDF; 428 kB) – E. A. Dinics Veröffentlichung des Algorithmus</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2018-07-08" href="https://de.wikipedia.org/wiki/?title=Algorithmus_von_Dinic&oldid=178968369">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>